List processing in a computer system refers to the operations such as inserting, removing, or searching for elements on a chained list of elements in storage. These chained lists are also called queues. FIG. 1 shows the structure of a typical chained list 2. The chained list 2 has a header 4 which contains status information about the list along with the address of the first element on the list. The chained list also includes a plurality of elements 6, 8, and 10. Elements adjacent in a chain are not necessarily contiguous in storage.
Each element contains an address field for encoding an address of the next element on the list, a field key for encoding a priority number, and a data field. The priority number in the key field is used to order the elements on the list. Elements could be placed on the list in ascending key sequence with the lowest value key first on the list, for example.
U.S. Pat. No. 4,177,513 filed July 8, 1977 discloses a computer system particularly suitable for processing such chained lists. The specification of U.S. Pat. No. 4,177,513 is incorporated herein by reference.
Among typical list-processing operations are operations to remove and insert elements in a chained list. An operation to remove an element having a desired key value would ordinarily include searching the list one element at a time until an element with the desired key value was located. This element would then be removed from the list by moving the address contained in the address field of the located element into the address field of the previous element on the chain. In this way the chain is made to bypass the removed element. Insert operations are ordinarily performed in a similar manner.
Because of the sequential nature of the insert and remove operations, and because chains can be extremely long, list processing operations can be very time consuming. For this reason, it is desirable for list processing operations to be interruptible to permit the computer to attend to other matters from time to time. One approach used in the past is to permit interrupts to occur between the processing of adjacent elements in the chain. If an interrupt does occur, the list-processing operation is aborted and later restarted from the beginning. The disadvantage of this approach is that if the chain is very long and interrupts sufficiently frequent, situations can arise in which the list-processing operations can never by completed.
Additional difficulties can arise if elements of a single chain are stored on different pages of a virtual memory storage system. In such a system, the address field of an element in a chain stored in main storage might reference an element in a page not presently located in main storage, but stored in a disk, for example. A search operation which encountered this address would generate a "page fault," which would result not only in the loading of the referenced page, but also in the restarting of the search. However, the page containing a previous element on the chain might have been removed from main storage to make room for the newly loaded page. Consequently, a second page fault would be generated before the originally referenced element was encountered. For very long chains it is possible that such page faulting and loading might become cyclical and the originally referenced element never reached. Such cyclical page faulting and loading behavior in a virtual memory system is termed "thrashing," and can be an extremely troublesome problem.
Interrupts are normally allowed only after execution of an instruction has been completed. Instructions have been made interruptable in the past such as a move instruction where the move is bounded. List processing instructions operate on unbounded lists and thus the interrupt problem is different and more difficult. Hence, in order to interrupt a list processing operation without aborting it, it is necessary to provide a means for recognizing a pending interrupt or event and for doing so during a particular time of the list processing operation. The present invention provides such a means which looks for pending interrupts during insert operations of list processing. Additionally, the status of the list processing operation must be saved and the identification of the task having the currently executing list processing instruction must be saved because other tasks having list processing instructions can normally access the list or queue. Because of this, and in order to preserve the integrity of the operation it is desirable to lock the list or queue from access by other tasks. If access by another task were allowed, that task could remove elements from the list or queue and thereby destroy the integrity. The present invention provides means for saving the aforementioned status, the identification of the task active during the list processing operation, means for locking the list or queue and means for unlocking the list or queue only when the interrupted task is again active.